Codeforces999 F. Cards and Joy

Posted on | In ,

有 $n*k$ 张牌，每张牌上写了数字，分给 $n$ 个人，每人 $k$ 张。每个人有一个喜欢的数字，分到 $i$ 张喜欢的牌，得到的价值就是$h[i]，$ 问所有人价值最大的总和

题解

因为每个人只有一张喜欢的牌，所以对答案有影响的是：以x牌为例，有多少个人喜欢x牌，有多少张x牌，有多少喜欢x牌人的人分配了x牌和每个人分配了几张

以每张牌的数量为01背包容量，喜欢的人数为物品数量，对每张牌做01背包即可

时间复杂度: 因为$f_i$的和$c_i$的总数都为 $10^5$, 故状态数不是很多